\documentclass[11pt]{article}
\usepackage{geometry}                % See geometry.pdf to learn the layout options. There are lots.
\geometry{letterpaper}                   % ... or a4paper or a5paper or ... 
%\geometry{landscape}                % Activate for for rotated page geometry
%\usepackage[parfill]{parskip}    % Activate to begin paragraphs with an empty line rather than an indent
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{epstopdf}
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png}

\title{DD2380 Project\\MINESWEEPER}
\author{Henrik Linde 760114\\Simon Pettersson 850128\\Svante Sundin 801108}
\date{}                                           % Activate to display a given date or no date

\begin{document}
\maketitle
\newpage
\section{Abstract}
This report aims to describe the work of solving the game Minesweeper with a smart agent, in the course Artificiel Intelligence DD2380. Minesweeper is a game where a player is moving around in a minefield trying to get through the field without stepping on a mine. The problem of solving the Minesweeper game were solved by formulating the problem as a constraint satisfaction problem (CSP). The CSP was solved by using a recursive backtracking search with forward checking and arc consistency checking. To keep the focus on solving the problem, Python programming language were used to implement the agent.
\newpage
\tableofcontents
\newpage
\section{Introduction}
Minesweeper is a game where one player explores a grid of squares by uncovering them each at a time. Squares are either unknown, not yet explored by the player, or uncovered displaying a figure from 0 through 8 providing the number of immediately adjacent mines. Mines, being the obstacle of Minesweeper are predistributed randomly over the square grid ahead of start. The game ends a loss whenever the player attempts to uncover an unknown square containing a mine. At start, each square is covered and unknown and at the goal, all squares but those containing mines are uncovered. Throughout the present report we will relate to an attempt to automate this solving procedure. Server software constituting the game platform as well as a compatible client is provided in advance. Our work will deal mainly with the decision makings of this client. Solving algorithms are all written with Python programming language.
\section{The Problem}
Designing an agent solving the Minesweeper problem is an interesting task which requires a healthy mix of guessing and deducing. Search spaces often tend to grow out of hand if not considered carefully, and may not even produce unambiguous results. Also while the total configuration of mines is generally undecidable until the goal is reached, portions of the game field often have enough information to make certain decisions. A good agent in this sense would therefor balance searching strategies on the one hand and guessing on the other so as to limit computational time.The perfect agent in a sense of safety-first would instead first consider the entire search space, that is all possible assignments of mines meeting constraints imposed by uncovered numbers. Strategies are needed both for appointing what squares to consider as well as for guessing. Lets say one were to test the assignment of a mine at the upper left square, assuring it meets constraints imposed by adjacent numbered squares and so on. It is then obvious that so doing may not always propagate further constraints onto other assignments throughout the play field, lets say for the lower right square. At first glance, it is easily seen that unknown squares may be related by constraints only if they belong to a certain class. Members of this class all have the property that the distance to some other member in terms coordinates, both horizontally and vertically is no greater than 2. Other independencies occur within these classes that are not so easily appointed in a systematic way. In fact, as soon as all possible assignments to any number of squares yield the same value for one of its squares in each and every assignment, it may then be decided for certain. When it comes to guessing, it is not always true that a greedy approach is the most fruitful. Lets say some probabilities are calculated by exhausting all possible assignments to a number of squares and then taking the average assignment. A greedy guess now means picking the square least probable to contain a mine. This still might not be the healthiest option for the chances of success since eventually a riskier square would have uncovered much better information and so on. All this being said, while the design of a good minesweeper agent may be a very intricate matter, we assure you dear reader that as we shall shortly demonstrate, a reasonably successful agent may come from the most naive approach.
\section{The Solution}
	To solve the problem we decided to use a constraint satisfaction prolem (CSP) formulation. This is because it seemed to fit our needs in the sense that it is easy to implement as long as a good formulation of the problem can be obtained. A CSP is defined by a set of variables $X_1,X_2,...X_n$ and a set of constraints $C_1,C_2,...C_n$. Each variable $X_i$ has a non empty domain $D_i$ of possible values. Each contraint $C_i$ involves some subset of the variables and specifies the allowable combinations of the values for the subset. A state of the problem is defined by an assignment of values to some or all of the variables, $\{X_i=v_i,X_j=v_j\}$. To fit this into the minesweeper problem we chose to define the variables $X_i$ as the visible numbers on the board. Every variable $X_i$ has a domain $D_i$ which assigns a mine $(1)$ or not mine $(0)$ to its neighboring, not opened squares. When the domains are assigned to the variables they are checked to be cosistent with the number in the square belonging to the variable, i.e. if a variable is said to have two mines and has three neighboring not opened squares, it's domain would consist of three sets of values $\{0,1,1\},\{1,0,1\},\{1,1,0\}$. The constraints $C_i$ prevents two variables sharing at least one not opened square to assign different values to that square. To reduce the size of the problem the fringe is divided in multiple parts where squares not dependent on each other doesn't end up in the same fringe. The fringes are then ordered by size, where the smallest one is solved first. The fringes are solved one at a time until one square without a mine is found. To solve the CSP we used a recursive backtracking search with forward checking and arc consistency checking. 
\section{The Implementation}
	The scripting language Python was chosen to implement the agent. This puts the fous on the problem at hand and not on implementation details. However, Python is slow in execution so it prevented us from using the solution we wanted to initially. Ideally one would like to find every possible solution to the CSP's but that is unfeasible for large problems and slow for small to medium ones. The agent was very slow even with the single solution method so we elected to not implement any of the more accurate ones. Another problem that Python itroduces is bugs related to its weak/dynamic nature. This is not really a big problem normally but when introduced to new programming challenges where code is frequently altered this can be a problem. The code was structured in an object oriented fashion where class instances represented the agent, the board, cells of the board, a CSP problem and the variables of the CSP problem. For convenience we used code authored by Peter Norvig to build our CSP solver base on, namely the Problem and CSP classes, as well as the backtracking search method. This is illustrated in Figure 1.
	\begin{figure}
		\caption{Block diagram of the agent.}
		\includegraphics[width=120mm]{uml.png}
	\end{figure}
\section{Obtained Results}
\begin{table}[h]
	\caption{Simulation results.}
	\begin{center}
		\begin{tabular}{| c | c | c | c | c |}
			\hline
			Board & Density & Won & Played & Average score\% \\
			\hline
			20x20 & 15\% & 1 & 100 & 13.5\% \\
			20x20 & 10\% & 19 & 100 & 56.5\% \\
			20x20 & 5\% & 73 & 100 & 87.01\% \\
			\hline
		\end{tabular}
	\end{center}
\end{table}
One important conclusion is that Python is an easy way to test and make prototypes, but the final code should be written in some other programing language, for instance C++. Some tests were run with different setups as shown in Table 1. From the table we can draw some conclusions. The agent is highly sensitive to the mine density of the field, this is because the nature of the "one solution" method used, that is, more mines adds more ambigousity to the solutions. The other conclusion is that it solves the simpler boards with a high success rate. To address the performance issues one might implement the agent in a faster, compiled programming language, but in the scope of this course the time just isn't there.  
\end{document}  
